package com.gxc.linkedList;

/**
 * 判断一个链表是否为回文结构
 * 后半链表选翻转
 */
public class IsPalindrome {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(1);
        node1.next = node2;
        node2.next = node3;
        System.out.println(handle(node1));

        ListNode node11 = new ListNode(1);
        ListNode node21 = new ListNode(2);
        ListNode node31 = new ListNode(2);
        ListNode node41 = new ListNode(2);
        node11.next = node21;
        node21.next = node31;
        node31.next = node41;
        System.out.println(handle(node11));
    }

    public static boolean handle(ListNode head) {
        if (head == null || head.next == null) return true;

        boolean res = true;
        //寻找中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next!=null && fast.next.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //中间节点后的节点反转
        ListNode node3 = null;
        fast = slow.next;
        slow.next = null;
        while (fast!=null) {
            node3 = fast.next;
            fast.next = slow;
            slow = fast;
            fast = node3;
        }
        //保存最后一个节点
        node3 = slow;
        fast = slow;
        slow = head;
        while (slow!=null && fast!=null) {
            if (slow.val!=fast.val) {
                res = false;
                break;
            }
            slow = slow.next;//左到中
            fast = fast.next;//右到中
        }

        fast = node3.next;
        slow = node3;
        node3.next = null;
        while (fast!=null) {
            node3 = fast.next;
            fast.next = slow;
            slow = fast;
            fast = node3;
        }

        return res;
    }

    public static class ListNode {
        int val;
        IsPalindrome.ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, IsPalindrome.ListNode next) { this.val = val; this.next = next; }
    }
}
